package alg

import "fmt"

func QuickSortRun() {
	//定义一个数组
	arr := []int{3, 1, 12, 7, 17, 30, 15, 50, 55, 76, 75}
	QuickSort(arr, 0, len(arr)-1)
	fmt.Println("main arr=", arr, "len=", len(arr))
}

// 快速排序, 属于划分交换排序, 采用分治法, 大规模的递归算法, 是归并排序的就地版本
// 快速排序 要比其他常见的排序算法要快, 但是因为是递归的, 所以在内存有限的机器不太适合
// 实现基本步骤和思想
// 1. 先区 数列 中的 某一个元素作为基准数(左边, 中间, 右边, 随机)
// 2. 根据基数对数列进行分区, 大于 基准数的元素放到右边, 小于基准数的元素放到左边, 最终分为两部分
// 3. 再对左右分区 重复 2 步骤, 直到区间只有一个元素
// 属于不稳定排序, 较复杂算法
// 时间复杂度: 最好:O(nlog2n), 最坏: O(n2), 平均: (nlog2n)
// 空间复杂度: O(log2n)
func QuickSort(arr []int, left, right int) {
	if left < right {
		i := adjustArrOnLeft(arr, left, right)
		QuickSort(arr, left, i-1)
		QuickSort(arr, i+1, right)
	}
}

// 根据 最左边元素基准 进行偏移
func adjustArrOnLeft(arr []int, left, right int) int {
	// 以最左边元素为基准
	x := arr[left]
	i, j := left, right
	for i < j {
		// 从右边 开始找小于 x 的元素
		for i < j && arr[j] >= x {
			j--
		}

		// 从左边找 大于 x 的元素
		for i < j && arr[i] <= x {
			i++
		}

		// 进行元素交换
		if i < j {
			fmt.Println("左边 i=", i, arr[i], ", 右边 j=", j, arr[j])
			arr[i], arr[j] = arr[j], arr[i]
		}
		fmt.Println("每次偏移 i,j=", i, j)
	}

	// 基准数归位
	arr[left], arr[i] = arr[i], arr[left]
	fmt.Println("返回基准 i=", i)
	return i
}

// 根据 中间元素基准 进行偏移
func adjustArrOnMid(arr []int, left, right int) int {
	// 以中间元素为基准
	mid := (left + right) / 2
	arr[left], arr[mid] = arr[mid], arr[left]
	x := arr[left]
	i, j := left, right
	for i < j {
		// 从右边 开始找小于 x 的元素
		for i < j && arr[j] >= x {
			j--
		}

		// 从左边找 大于 x 的元素
		for i < j && arr[i] <= x {
			i++
		}

		// 进行 元素交换
		if i < j {
			fmt.Println("左边 i=", i, arr[i], ", 右边 j=", j, arr[j])
			arr[i], arr[j] = arr[j], arr[i]
		}
	}

	// 基准数归位
	arr[left], arr[i] = arr[i], arr[left]
	fmt.Println("返回基准 i=", i)
	return i
}

// 根据 中间元素基准 进行偏移
func adjustArrOnRight(arr []int, left, right int) int {
	// 以最右边元素为基准
	arr[left], arr[right] = arr[right], arr[left]
	x := arr[left]
	i, j := left, right
	for i < j {
		// 从右边 开始找小于 x 的元素
		for i < j && arr[j] >= x {
			j--
		}

		// 从左边找 大于 x 的元素
		for i < j && arr[i] <= x {
			i++
		}

		// 进行 元素交换
		if i < j {
			fmt.Println("左边 i=", i, arr[i], ", 右边 j=", j, arr[j])
			arr[i], arr[j] = arr[j], arr[i]
		}
	}

	// 基准数归位
	arr[left], arr[i] = arr[i], arr[left]
	fmt.Println("返回基准 i=", i)
	return i
}
